#include<stdio.h>
#include<malloc.h>

struct list
{
	int value;
	struct list *next,*prev;
};
struct list *first=NULL;

int main()
{
	int *a=NULL,b,c=1,opt1,opt2,i,j,n,temp,sum,location;
	int *a1=NULL,flag;	
	int temp1=0,temp2,pos,ele;
	static int m=0;
	struct list *new_node,*p,*q,*cur,*pre,*temp3,*first1,*r;
	struct list *w1=NULL,*w2=NULL,*w3=NULL,*w4=NULL,*w5=NULL;
	do
	{	
		printf("\t\tMENU\n\n");
		printf("1. Create list using arrays\n");
		printf("2. Create list using linked list\n");
		printf("3. Exit\n\n");
		printf("Enter option: ");
		scanf("%d",&opt1);
		switch(opt1)
		{
			case 1: do
				{
					printf("\n\n\t\tMENU\n\n");	
					printf("1. Add elements into the List\n");
					printf("2. View the List\n");
					printf("3. Sort the List\n");
					printf("4. Remove an element from the List\n");	
					printf("5. Count the number of elements in the List\n");
					printf("6. Search for an element in the List\n");
					printf("7. Reverse the List\n");	
					printf("8. Extend the list\n");
					printf("9. Insert an element at a given position in the List\n");
					printf("10. Pop an element from a given position in the List\n");
					printf("11. Exit\n\n");
					printf("Enter option: ");
					scanf("%d",&opt2);
					switch(opt2)
					{
						case 1: do
							{	
								a=(int *)realloc(a,(m * sizeof(int)));
								printf("Enter the element to be inserted: ");
								scanf("%d",&a[m]);
								m++;	
								printf("Do you want to enter more elements?(1 to enter more elements, 0 to quit): ");
								scanf("%d",&c);
							}while(c!=0);
							break;
						case 2: if(a==NULL)
								printf("The list is empty!\n");
							else
							{
								printf("The list is ");
								for(i=0;i<m;i++)
								{
									printf("%d ",a[i]);
								}
								printf("\n");
							}	
							break;
						case 3: if(a==NULL)
								printf("The list is empty!\n");
							else
							{
								printf("\nEnter 1 if you want to sort in ascending order and 2 if you want to sort in descending order: ");
								scanf("%d",&n);
								switch(n)
								{
									case 1:	for(i=1;i<m;i++)                                        //ascending order
										{
											for(j=0;j<i;j++)
											{
												if(a[i]<a[j])
												{
													temp=a[i];
													a[i]=a[j];
													a[j]=temp;
												}	
												else
													continue;
											}
										}
										break;
									case 2:	for(i=1;i<m;i++)					//descending order
										{
											for(j=0;j<i;j++)
											{				
												if(a[i]>a[j])					
												{
													temp=a[i];
													a[i]=a[j];
													a[j]=temp;
												}
												else
													continue;
											}
										}	
										break;
									default: printf("\nWrong option entered!\n");
									 	break;	
								}
								printf("The List after sorting is ");
								for(i=0;i<m;i++)
								{
									printf("%d ",a[i]);
								}
							}
							break;
						case 4: if(a==NULL)
								printf("The list is empty!\n");
							else
							{
								do
								{	
									printf("Enter the element you want to remove from the list: ");
									scanf("%d",&b);
									for(i=0;i<m;i++)
									{
										if(a[i]==b)
										{
											for(j=i+1;j<m;j++)
											{
												a[j-1]=a[j];
											}
										break;	
										}
									}
									if(i==m)
									{
										printf("The element was not found in the list!\n\n");
									}
									else
									{
										--m;
										a=(int *)realloc(a,m*sizeof(int));
										printf("The new list is ");
										for(i=0;i<m;i++)
										{
											printf("%d ",a[i]);
										}
										printf("\n\n");
									}
									printf("Do you want to delete more elements?(1 to delete more elements, 0 to quit): ");
									scanf("%d",&c);	
								}while(c!=0);
							}							
							break;
						case 5: if(a==NULL)
								printf("The list is empty!\n");
							else
							{
								printf("\nThere are %d elements in the List\n",m);
							}
							break;
						case 6: if(a==NULL)
								printf("The list is empty!\n");
							else
							{
								printf("Enter the element you want to search for: ");
								scanf("%d",&b);	
								for(i=0;i<m;i++)
								{
									if(a[i]==b)
									{
										printf("\nThe element %d was found at index %d of the List\n\n",b,(i+1));
										break;
									}
								}
								if(i==m)
								{
									printf("\nElement was not found in the List!\n\n");
								}
							}
							break;
						case 7: if(a==NULL)
								printf("The list is empty!\n");
							else
							{		
								n=m/2;
								for(i=0,j=(m-1);i<=n,j>=n;i++,j--)
								{
									temp=a[j];
									a[j]=a[i];
									a[i]=temp;
								}
								printf("The reversed list is ");
								for(i=0;i<m;i++)
								{
									printf("%d ",a[i]);
								}
							}
							break;
						case 8: if(a==NULL)
								printf("The list is empty!\n");
							else
							{
								do
								{	
									a1=(int *)realloc(a1,(temp1 * sizeof(int)));
									printf("Enter the element to be inserted into the temporary list: ");
									scanf("%d",&a1[temp1]);
									temp1++;	
									printf("Do you want to enter more elements?(1 to enter more elements, 0 to quit): ");
									scanf("%d",&c);
								}while(c!=0);
								temp2=m;
								m+=temp1;
								a=(int *)realloc(a,m*sizeof(int));
								for(i=temp2,j=0;i<m,j<temp1;i++,j++)
								{
									a[i]=a1[j];
								}
								printf("\nAfter adding the temporary list, the extended list is ");
								for(i=0;i<m;i++)
								{
									printf("%d ",a[i]);
								}
							}
							break;
						case 9: if(a==NULL)
								printf("The list is empty!\n");
							else
							{
								printf("Enter index where you want to add an element ");
								scanf("%d",&pos);	
								if(pos>m)
								{
									printf("Not possible to insert element at position that is out of range of list!\n");
									break;
								}
								else
								{
									printf("Enter element you want to insert ");
									scanf("%d",&ele);
									m+=1;
									a=(int *)realloc(a,m*sizeof(int));
									for(i=m;i>pos;i--)
									{
										a[i]=a[i-1];
									}
									a[pos]=ele;
								}
								printf("The List after inserting element is ");
								for(i=0;i<m;i++)
								{
									printf("%d ",a[i]);
								}
							}
							break;
						case 10:if(a==NULL)
								printf("The list is empty!\n");
							else
							{
								printf("Enter index from where you want to pop an element ");	
								scanf("%d",&pos);	
								if(pos>m)
								{
									printf("Not possible to pop element at position that is out of range of list!\n");
									break;
								}
								else
								{
									printf("The popped element is %d\n",a[pos]);
									for(i=pos;i<m;i++)
									{
										a[i]=a[i+1];
									}
									m-=1;
									a=(int *)realloc(a,m*sizeof(int));
								}
								printf("The List after popping element is ");
								for(i=0;i<m;i++)
								{
									printf("%d ",a[i]);
								}
							}
							break;
						case 11: return 0;
						default: printf("Wrong option entered. Please enter again: ");	
							 break;
					}
				}while(opt2!=11);
				break;
			case 2: do
				{
					printf("\n\n\t\tMENU\n\n");	
					printf("1. Add elements into the List\n");
					printf("2. View the List\n");
					printf("3. Remove an element from the List\n");	
					printf("4. Count the number of elements in the List\n");
					printf("5. Search for an element in the List\n");
					printf("6. Reverse the List\n");
					printf("7. Sort the List\n");
					printf("8. Extend the List\n");
					printf("9. Insert an element at a given position in the List \n");
					printf("10. Pop an element from a given position in the List\n");
					printf("11. Exit\n\n");
					printf("Enter option: ");		
					scanf("%d",&b);
					switch(b)
					{
						case 1: new_node=malloc(sizeof(struct list));
							printf("Enter a new value: ");		
							scanf("%d",&new_node->value);
							first=new_node;				
							p=first;
							first->next=NULL;
							first->prev=NULL;
							printf("Do you want to enter more values?(1 to enter more values, 0 to quit): ");
							scanf("%d",&c);
							if(c==1)
							{	
								do
								{		
									struct list *new_node;		
									new_node=malloc(sizeof(struct list));	
									printf("Enter a new value: ");		
									scanf("%d",&new_node->value);
									q=new_node;
									p->next = q;
									q->prev = p;
									p = q;
									printf("Do you want to enter more values?(1 to enter more elements, 0 to quit): ");
									scanf("%d",&c);
								}while(c!=0);
							}							
							else
								break;
							break;
						case 2: if(first==NULL)
								printf("List is empty!\n");
							else
							{
								p=first;
								printf("List is: ");
								while(p!=NULL)
								{
									printf("%d ",p->value);
									p=p->next;
								}
							}	
							break;
						case 3: if(first==NULL)
								printf("List is empty!\n");
							else
							{
								printf("Enter the element you want to delete: ");
								scanf("%d",&n);
								for(cur=first,pre=NULL;cur!=NULL && cur->value!=n;pre=cur,cur=cur->next);
								{
									if(cur==NULL)
									{		
										printf("Element was not found!\n");
										p=first;
										printf("List is: ");
										while(p!=NULL)
										{
											printf("%d ",p->value);
											p=p->next;
										}
									}		
									if(pre==NULL)
										first=first->next;
									else
										pre->next=cur->next;
									free(cur);
									p=first;
									printf("List is: ");
									while(p!=NULL)
									{
										printf("%d ",p->value);
										p=p->next;
									}
								}
							}
							break;
						case 4: if(first==NULL)
								printf("List is empty!\n");
							else
							{
								p=first;
								sum=0;
								while(p!=NULL)
								{
									sum+=1;
									p=p->next;
								}	
								printf("The number of elements in the list is %d\n\n",sum);
							}
							break;
						case 5: if(first==NULL)
								printf("List is empty!\n");
							else
							{	
								location=0;
								p=first;
								printf("Enter the element you want to search for: ");
								scanf("%d",&n);
								while(p!=NULL)
								{
									location+=1;
									if(p->value==n)
									{
										printf("Element %d has been found at index %d\n\n",n,location);
										break;
									}
									else
									{
										p=p->next;
									}
								}
								if(p==NULL)
									printf("Element was not found in the list!\n\n");
							}				
							break;
						case 6: if(first==NULL)
								printf("List is empty!\n");
							else
							{
								p=q;
								printf("Reverse List is: ");
								while(p!=NULL)
								{
									printf("%d ",p->value);
									p=p->prev;
								}
							}				
							break;
						case 7: while(w4 != first->next) 
							{
	 							w3 = w1 = first;
		 						w2 = w1->next;
		  						while(w1 != w4) 
								{
		  							if(w1->value > w2->value) 
									{
			   							if(w1 == first) 
										{
				    							w5 = w2 -> next;
   											w2->next = w1;
    											w1->next = w5;
    						 					first = w2;
   						  					w3 = w2;
   						 				} 
										else 
										{
				    							w5 = w2->next;
    						 					w2->next = w1;
    						 					w1->next = w5;
   						  					w3->next = w2;
  						   					w3 = w2;
  						  				}
   									} 
									else 
									{
   						 				w3 = w1;
   						 				w1 = w1->next;
  						 			}
  						 			w2 = w1->next;
  						 			if(w2 == w4)
  						  				w4 = w1;
 						 		}
 							}
							struct list *o;
							o=first;
							q=first;
							q->prev=NULL;
							printf("Sorted list is ");
							while(o!=NULL)
							{
								printf("%d ",o->value);
								if(o->next!=NULL)								
								{									
									q=o->next;
									q->prev=o;								
								}							
								o=o->next;
							}
							break;
						case 8: if(first==NULL)
								printf("List is empty!\n");
							else
							{
								new_node=malloc(sizeof(struct list));	
								printf("Enter a new value: ");		
								scanf("%d",&new_node->value);
								first1=new_node;
								r=first1;	
								first1->next=NULL;
								first1->prev=NULL;
								printf("Do you want to enter more values to the temporary list?(1 to enter more values, 0 to quit): ");
								scanf("%d",&c);
								if(c==1)
								{	
									do
									{		
										struct list *new_node;		
										new_node=malloc(sizeof(struct list));	
										printf("Enter a new value: ");		
										scanf("%d",&new_node->value);
										q=new_node;
										r->next = q;
										q->prev = r;
										r = q;
										printf("Do you want to enter more values to the temporary list?(1 to enter more elements, 0 to quit): ");
										scanf("%d",&c);
									}while(c!=0);
									temp3=p=first;
									while((p->next)!=NULL)
									{
										p=p->next;
									}
									first1->prev=p;
									p->next=first1;
									printf("Extended List is: ");
									while(temp3!=NULL)
									{
										printf("%d ",temp3->value);
										temp3=temp3->next;
									}
								}							
								else
									break;
							}
							break;
						case 9: if(first==NULL)
								printf("List is empty!\n");
							else
							{
								printf("Enter the index where you want to add the element: ");
								scanf("%d",&pos);
								j=0;
								cur=first;
								pre=NULL;
								flag=0;
								while(cur!=NULL)
								{
									if(j==pos && pre!=NULL)
									{
										new_node=malloc(sizeof(struct list));
										printf("Enter the element you want to add: ");
										scanf("%d",&new_node->value);		
										temp3=cur;  
										cur=new_node;	
										pre->next=cur;
										cur->next=temp3;
										flag=1;	
										break;							
									}	
									else if(j==pos && pre==NULL)
									{
										new_node=malloc(sizeof(struct list));
										printf("Enter the element you want to add: ");
										scanf("%d",&new_node->value);	
										temp3=first;
										first=new_node;
										first->next=temp3;
										flag=1;
										break;
									}
									j++;
									pre=cur;
									cur=cur->next;							
								}
								if(flag==0)
								{		
									printf("Index is out of range, element cannot be inserted!\n");
									break;
								}	
								p=first;
								printf("New List is: ");
								while(p!=NULL)
								{
									printf("%d ",p->value);	
									p=p->next;
								}
							}
							break;
						case 10:if(first==NULL)
								printf("List is empty!\n");
							else
							{
								printf("Enter the index where you want to pop the element: ");
								scanf("%d",&pos);
								j=0;
								cur=first;
								pre=NULL;
								flag=0;
								while(cur!=NULL)
								{
									if(j==pos && pre!=NULL)
									{	
										pre->next=cur->next;
										flag=1;
										printf("\nPopped element is %d\n",cur->value);	
										free(cur);
										break;							
									}	
									else if(j==pos && pre==NULL)
									{
										first=first->next;
										printf("\nPopped element is %d\n",cur->value);
										free(cur);								
										flag=1;
										break;
									}
									j++;
									pre=cur;
									cur=cur->next;							
								}
								if(flag==0)
								{		
									printf("Index is out of range, element cannot be popped!\n");
									break;
								}	
								p=first;
								printf("New List is: ");
								while(p!=NULL)
								{
									printf("%d ",p->value);	
									p=p->next;
								}
							}
							break;
						case 11: return 0;
						default: printf("Wrong option entered. Please enter again: ");	
							 break;
					}
				}while(b!=11);
				break;
			case 3: return 0;
			default: printf("Wrong option entered. Please enter again: ");	
				 break;
		}
	}while(opt1!=3);
}
